#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord,
        vector<string>& wordList) {
        unordered_set<string> wordList_set(wordList.begin(), wordList.end());
        unordered_set<string> vis;
        int len = beginWord.size();

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        int ret = 1;
        while (!q.empty()) {
            int ct = q.size();
            while (ct--) {
                string front = q.front();
                if (front == endWord) {
                    return ret;
                }
                q.pop();
                for (int i = 0; i < len; i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c != front[i]) {
                            string tmp = front;
                            tmp[i] = c;
                            if (!vis.count(tmp) && wordList_set.count(tmp)) {
                                q.push(tmp);
                                vis.insert(tmp);
                            }
                        }
                    }
                }
            }
            ret++;
        }

        return 0;
    }
};